Diseño Y Análisis De Algoritmos

1 Contenido de la clase

Repaso: caminos y pesos en un grafo [00:00-09:45]

La clase comienza como continuación de la sesión anterior. Se trabaja sobre un grafo y se identifican caminos: "vamos a poner el camino" [01:54]; se menciona un camino 3, 2, 3, 1 y otro 3, 2, 3, 4, 6 [02:09-02:18]. Se van asignando pesos a las aristas ("vamos a poner pesos" [05:23]) y se pregunta "¿cuál es el peso de este camino?" [06:01]. La clase opera sobre una representación del grafo por listas, a las que se les colocan los pesos ("esto es el de los pesos" [08:53]). [parte no entendida en varios pasajes de este repaso.]

Los estados del grafo: las zonas de color [22:55-29:57]

"Esto es un poco de color, que son los estados" [22:55]: cada vértice del grafo tiene un estado representado con un color. Existe una zona negra, formada por los vértices que ya están resueltos ("son los vértices que tengo ya antes" [24:17]). Se van anotando etiquetas en los vértices (en el ejemplo aparecen etiquetas P1, P2, … [23:41-23:49]) y en cada paso "hay que tomar el mínimo de estos" [24:01]. La zona negra no es fija: "originalmente la zona negra es aquí… hay que actualizar la zona negra" [28:38-28:44], y también "todavía hay que actualizar aquí las etiquetas" [28:26]. La idea es "encontrar el label más chico" [29:26]. [parte no entendida en el detalle del recorrido.]

Inicialización: los vecinos de la fuente [40:00-40:43]

"Inicialmente tiene que ser uno de los vecinos de la raíz; esos serían los 6" [40:18-40:22]. "Ahora cada uno de estos vecinos va a tener un peso, que va a ser igual a la longitud de la arista" [40:23-40:29]: al arrancar, cada vecino del vértice inicial recibe como etiqueta el peso (longitud) de la arista que lo une con la fuente.

El bucle principal: elegir el menor, "volver negro" y actualizar [41:16-47:55]

En cada paso se consideran los vecinos del vértice recién resuelto ("vamos a hacer estos, los vecinos de este lado… se va a poder encontrar por los vecinos de este lado" [41:16-41:28]; "serían tres vecinos por acá" [41:36]). El vértice de menor etiqueta pasa a la zona resuelta: "este se vuelve negro, este se vuelve negro, y este se vuelve negro" [47:07-47:20], es decir "ya encontraste el menor peso" [47:20]. Después se actualizan las etiquetas de sus vecinos sumando el peso de la arista a la etiqueta actual: "sería 2 más 3" [45:29-45:32]; "yo diría que 3 más 3 sería" [46:52]. La zona roja (vértices recién descubiertos) también cambia: "la zona roja ¿va a cambiar?" [45:36-45:37]. [parte no entendida en algunos pasajes del recorrido.]

Reconstrucción del camino [42:24-42:50]

Al terminar se puede leer el camino seguido: "sería el camino de este" [42:24]. El peso total del camino se obtiene sumando los pesos de las aristas que lo forman: "¿cuánto tiempo tomaría? … sería esto más esto" [42:47-42:50].

¿Cuánto cuesta el algoritmo? [48:55-49:49]

Se discute informalmente el costo: "yo diría que es la suma de los lados" [49:15] y "¿cuántos pasos vamos a hacer? Yo diría que sería de 1 o 2" [49:29-49:31]. La estimación es del orden del número de aristas: "básicamente el número de aristas por 2" [49:35-49:43]; es decir, en el recorrido cada arista se atiende un número pequeño constante de veces.

Cierre: el famoso algoritmo de Dijkstra [60:00-64:04]

Se retoma el avance "siguiendo la zona negra" [61:10] y los vértices que van quedando "adyacentes" [61:18]. Al final el profesor cierra: "este sería el famoso algoritmo de Dijkstra" [62:48] — el método explicado en la pizarra es el algoritmo de Dijkstra para el camino más corto. El último tramo discute detalles de la implementación, pero es prácticamente inaudible. [parte no entendida — tramo final 63:35-64:04.]

2 Puntos destacados / Lo que hay que saber

3 Actividades y tareas pendientes

En esta clase no se dejó ninguna tarea concreta con fecha de entrega. Conviene practicar por cuenta propia:

4 Dudas que podrían examinar

5 Sitios o recursos para visitar

El profesor no citó libros, páginas ni herramientas concretas en esta clase. Recursos útiles para profundizar lo explicado:

6 Glosario de términos

• Grafo con pesos: grafo en el que cada arista tiene asociado un valor numérico (peso).
• Camino más corto: camino de menor peso total entre dos vértices.
• Fuente (raíz): vértice inicial desde el cual se calculan las distancias.
• Etiqueta: distancia acumulada (provisional) que se le va asignando a cada vértice.
• Zona negra: conjunto de vértices cuya distancia ya es definitiva (resueltos).
• Zona roja: vértices que ya fueron descubiertos pero aún no resueltos.
• Zona verde: vértices todavía no visitados.
• Actualizar etiqueta: calcular el nuevo valor de un vértice (etiqueta actual + peso de la arista) y quedarse con el menor.
• Algoritmo de Dijkstra: algoritmo voraz que calcula el camino más corto desde una fuente en un grafo con pesos no negativos.

7 Mapa mental textual

• Diseño Y Análisis De Algoritmos · Clase 7
  • Camino más corto en grafos con pesos
    • Grafo con pesos, caminos y peso total de un camino
  • Estados de los vértices (zonas de color)
    • Zona negra: vértices resueltos
    • Zona roja: vértices descubiertos
    • Zona verde: vértices por visitar
  • Algoritmo de Dijkstra
    • Inicializar los vecinos de la fuente con el peso de la arista
    • Elegir el vértice de menor etiqueta (el mínimo)
    • El vértice "se vuelve negro" (pasa a resueltos)
    • Actualizar etiquetas de sus vecinos (etiqueta + peso de la arista)
    • Repetir hasta cubrir todos los vértices
  • Reconstrucción del camino
    • Suma de los pesos de las aristas
  • Costo
    • Del orden del número de aristas